/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <queue> 
#include <stack>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

// 遍历
// template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit_arr(vector<int>& arr, string const str){
    vector<int>::iterator it;
    cout << str << ": ";
    for(it=arr.begin();it!=arr.end();++it){
        cout << *it <<" ";
    }
    cout<<endl;
}
// 遍历
// template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit2_arr(vector<int>& arr, string const str){
    cout << str << ": ";
    for(int i; i < arr.size(); ++i){
        cout << arr[i] << " ";
    }
    cout<<endl;
}



// 链表结点
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void visit_list(ListNode* head){
    ListNode* tmp = head;
    while(tmp != nullptr){
        cout << tmp->val << ' ';
        tmp = tmp->next;
    }
    cout << endl;
}

// 二叉树--孩子兄弟表示法
//Definition for a binary tree node.// 二叉树--孩子兄弟表示法
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


// class Solution {
// public:
//     int purchasePlans(vector<int>& nums, int target) {
//         int ans = 0;
//         int len = nums.size();
//         sort(nums.begin(), nums.end());
//         visit_arr(nums, "sort");
//         int i, j;
//         for (i = len-1; nums[i] > target && i > 0;--i);
//         int startj = i;
//         if (startj<=0)
//             return 0;
//         cout << "startj: " << startj << endl;
//         for (i = 0, j = startj; i <= len && nums[i] <= target  && j>i; ++i)
//         {
//             for (j = startj; nums[j] + nums[i] > target && j>i;--j);
//             cout << " i: " << i << " j: " << j << endl;
//             if (j!=i)
//                 ans += (j - i);
//         }
//         return ans % (int)(1e9 + 7);
//     }
// };

class Solution {
public:
    int purchasePlans(vector<int>& nums, int target) {
        long int ans = 0;
        int len = nums.size();
        sort(nums.begin(), nums.end());
        // visit_arr(nums, "sort");
        int i, j;
        for (i = len-1; nums[i] > target && i > 0;--i);
        int startj = i;
        if (startj<=0)
            return 0;
        cout << "startj: " << startj << endl;
        // for (i = 0, j = startj; i < len && nums[i] <= target  && j>i ;)
        for (i = 0, j = startj; j>i ;)
        {
            if (nums[j] + nums[i] > target)
                --j;
            else {
                ans += (j - i);
                ++i;
            }
            cout << " i: " << i << " j: " << j << endl;
        }
        return ans % (int)(1e9 + 7);
    }
};


int main(int argc, const char** argv) {
    Solution solu = Solution();
    // vector<int> nums = {2,5,3,5};
    // int target = 6;
    // vector<int> nums = {3,1,2};
    // int target = 5;
    vector<int> nums = {61055,35718,71455,34429,97039,63942,37037,88911};
    int target = 17209;
    // vector<int> nums = {2,2,1,9};
    // int target = 10;
    cout << solu.purchasePlans(nums, target) << endl;

    return 0;
}